package com.heng.test;

import java.lang.String;
import java.util.ArrayList;
import java.util.Arrays;

public class LCA {
    static ArrayList[] e = new ArrayList[10];
    static int[][] fa = new int[10][20];
    static int[] dep = new int[10];

    static void dfs(int u, int father) {
        dep[u] = dep[father]+1;
        fa[u][0]=father;
        for (int i = 1; i < 20; i++) {
            fa[u][i]=fa[fa[u][i-1]][i-1];
        }
        for (int i = 0; i < e[u].size(); i++) {
            int v =(Integer) e[u].get(i);
            if(v!=father)dfs(v,u);
        }
    }

    static int lca(int u, int v) {
        if(dep[u] < dep[v]) {
            int temp = u;
            u = v;
            v= temp;
        }
        for (int i = 19; i >= 0 ; i--) {
            if(dep[fa[u][i]]>=dep[v]) u = fa[u][i];
        }
        if(u==v)return v;
        for (int i = 19; i>=0;i--) {
            if(fa[u][i]!=fa[v][i]){
                u = fa[u][i];
                v=fa[v][i];
            }

        }

        return fa[u][0];
    }

    public static void main(String[] args) {
        for (int i = 0; i < e.length; i++) {
            e[i] = new ArrayList();
        }
        e[1].add(5);
        e[1].add(4);

        e[3].add(9);

        e[5].add(2);
        e[5].add(6);
        e[5].add(7);

        e[6].add(3);
        e[6].add(8);

        dfs(1,0);

        System.out.println(Arrays.toString(fa[3]));
        System.out.println(Arrays.toString(dep));
        System.out.println(lca(2, 7));
    }
}
